% Before going into the details of our approach, we like to briefly introduce 
% the overall architecture of our framework in section~\ref{architecture} 
% and detail the metadata and data management components in 
% section~\ref{data-management}. 
% 
% \subsection{Plugin-based processing pipeline}
% \label{architecture}
% 
% The core of our system is a framework for federated search. On top we built 
%  abstractions for declarative question answering (Q\&A) 
%  as explained later on. The system follows 
% a plugin-based architecture \cite{conf/eurocast/WagnerWPKBBA07}. 
% We distinguish three types of plugins, each type responsible for one 
% processing step within our system: extracting information from the 
% user's question, formulating and executing a structured query, and
% post-processing the result by rendering a chart. All plugins within a
% certain processing step are executed independently of each other, 
% which allows a huge degree of parallelism as explained in
% section~\ref{sec:execution}.
% The three different plugin types are:
% 
% \textbf{(1) Information Extraction Plugins:} The first type of plugin analyzes
%  the user's question by triggering information extraction components. These
%  components contribute to a common data structure, the so-called \emph{parse 
%  graph} (see next subsection). By default, the system is equipped with three
%  types of information extraction plugins that can be instantiated for 
%  different data sources or configurations (see also 
%  section~\ref{information-extraction}). These are: plugins for matching 
%  artifacts of the data source's metadata within the query, plugins for 
%  recognizing data values (directly executed inside the underlying database) 
%  and plugins for applying natural language patterns (e.g., for range 
%  queries). These plugins jointly capture lower-level semantic information to
%  interpret a user's question in the context of the data warehouse metadata. 
%  %in subsequent processing steps.
%  
% \textbf{(2) Search Plugins:} Search plugins operate on the common result of all
% information extraction plugins -- the \emph{parse graph}\footnote{See
% section~\ref{data-management}}.
% The name \emph{Search Plugin} is used because their intent is to execute some
% kind of queries on some back-end system, which could be a traditional
% search engine in the scope of the federated search framework. 
% They may use recognized semantics from the parse graph and 
% formulate arbitrary types of queries. In the case of leveraging
% a traditional search engine, a plugin might take the users' question, rewrite
% it using the recognized semantics to achieve higher recall or
% precision.
% However, for Q\&A we define an abstract implementation of a plugin that is
% equipped with algorithms to transform the semantics captured in the \emph{parse graph}
% to a structured query (see section~\ref{sec:structural-constraints}). The
% output of a search plugin is a stream of objects representing a 
% well-structured result together with its metadata 
% consisting of the datasource that was used to retrieve the object
%  and a score computed inside the plugin.
% 
% \textbf{(3) Post-processing Plugins:} Post-processing plugins might be used
% for different purposes. They can alter the resulting objects in an arbitrary 
% way (or even aggregate different results). The main funtionality of 
% post-processing plugins in the application presented in this paper is
% to 
% %select 
% render
% appropriate chart types for a given result object 
% (see~\cite{text2query}).
% % and render a corresponding image.
%  
% 
% \subsection{Metadata Management and Parse Graphs}
% \label{data-management}


\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[remember picture]
\tikzstyle{bigbox} = [draw, draw=black!20, rounded corners, rectangle]
\tikzstyle{boxed} = [minimum height=0.8cm, draw=black!50, rounded corners, rectangle] 
\tikzstyle{unboxed} = [minimum height=0.8cm,rounded corners, rectangle] 
\tikzstyle{node}=[circle,minimum size=10pt,draw=black, font=\tiny] 
\tikzstyle{blind}=[]
\tikzstyle{title} =[fill=white, text=black!80]
\tikzstyle{edge} = [->,text=black]
% user profile graph
  	\node[node, fill=blue!10](userNode){U};
  	\node[unboxed,left of=userNode,node	distance=1.1cm](userNodeLabel){User\#123}; 
  	\node[blind,left of=userNode,node distance=3.5cm](userProfileLeft){}; 
  	\node[blind,right of=userNode,node distance=3.5cm](userProfileRight){};
  	%
  	\node[node, below of=userNode,node distance=2cm, fill=blue!10](userName){?};
	\node[unboxed,below of=userName,node distance=.4cm](userNameLabel){John
	Smith};
	%
  	\node[node, left of=userName,node distance=2cm, fill=blue!10](userLocale){?};
	\node[unboxed,below of=userLocale,node distance=.4cm](userLocaleLabel){US};  
	%
  	\node[node, right of=userName,node distance=2cm, fill=blue!10](userCity){?};
	\node[unboxed,below of=userCity,node distance=.4cm](userCityLabel){Palo Alto};  			
	% 		
	\path[edge] (userNode) edge node {name} (userName);
	\path[edge,left=.1pt] (userNode) edge node {locale} (userLocale);
	\path[edge,right=.1pt] (userNode) edge node {location} (userCity);
% user profile box
\node[bigbox, fit=(userNode) (userName) (userLocale) (userCity)
(userNameLabel) (userLocaleLabel) (userCityLabel)(userNodeLabel)
(userProfileLeft)(userProfileRight)](userProfile) {};
\node[title, right=10pt, font=\large] at (userProfile.north west) {User Profile};

% schema graph
  	\node[node](schemaNode)[below of=userNode,node distance=3.7cm,
  	fill=red!10]{W}; \node[unboxed,right of=schemaNode,node
  	distance=.9cm](schemaNodeLabel){Resorts}; \node[blind,left
  	of=schemaNode,node distance=3.5cm](schemaNodeLeft){}; \node[blind,right
  	of=schemaNode,node distance=3.5cm](schemaNodeRight){};
  	%
  	\node[node, left of=schemaNode,node distance=2cm,fill=red!10](revenueNode){M};
	\node[unboxed,below left of=revenueNode,node
	distance=.6cm](revenueNodeLabel){Revenue};

  	%
  	\node[node, below of=schemaNode,node distance=2cm,fill=red!10](customerNode){D};
	\node[unboxed,below left of=customerNode,node
	distance=.6cm](customerNodeLabel) {Customer};
	%
  	\node[node, left of=customerNode,node distance=2cm,fill=red!10](ageNode){A};
	\node[unboxed,left of=ageNode,node distance=.6cm](ageNodeLabel) {Age};
	%
  	\node[node, right of=customerNode,node distance=2cm,fill=red!10](cityNode){D};
	\node[unboxed,below left of=cityNode,node distance=.6cm](cityNodeLabel){City};  
	% 		
	\path[edge,left=.1pt] (customerNode) edge node {dimOf} (schemaNode);
	\path[edge,above=.1pt] (ageNode) edge node {attrOf} (customerNode);
	\path[edge] (cityNode) edge node {dimOf} (schemaNode);
	\path[edge,above=.1pt] (revenueNode) edge node {measOf} (schemaNode);
% schema box
\node[bigbox, fit=(schemaNode) (customerNode) (cityNode) (revenueNode)
(schemaNodeLabel) (customerNodeLabel) (cityNodeLabel)(revenueNodeLabel)
(schemaNodeLeft)(schemaNodeRight)](metadata) {};
\node[title, right=10pt, font=\large] at (metadata.north west) {Schema};

% parse graph
	\node[node,fill=yellow!30, below of=schemaNode,node
	distance=5.4cm, font=\large](queryNode){Q}; \node[blind,left of=queryNode,node
	distance=3.5cm](queryNodeLeft){}; \node[blind,right of=queryNode,node
	distance=3.5cm](queryNodeRight){};
    %
    \node[boxed,below of=queryNode,node distance=1.5cm](txtTop5){Top 5};
    \node[boxed,left of=queryNode,node
    distance=2cm](txtMiddleAged){middle-aged}; \node[boxed,above
    of=queryNode,node distance=1.5cm](txtCustomer){customers};
    \node[boxed,right of=queryNode,node distance=2cm](txtMyCity){my city};
    %
    \path[edge] (queryNode) edge node {hasAnnot} (txtTop5);
    \path[edge,above=.1pt] (queryNode) edge node {} (txtMiddleAged);
    \path[edge] (queryNode) edge node {hasAnnot} (txtCustomer);
    \path[edge,above=.1pt] (queryNode) edge node {} (txtMyCity);
% parse graph box
\node[bigbox, fit=(queryNode)(txtMiddleAged)(txtTop5) (txtCustomer) (txtMyCity)
(queryNodeLeft)(queryNodeRight)](question) {};
\node[title, right=10pt, font=\large] at (question.north west) {Parse Graph};

% pattern graph
	\node[node, below of=queryNode,node
	distance=4.7cm,fill=green!10](patternNode){C}; \node[unboxed,below
	of=patternNode,node distance=.6cm](patternNodeLabel){PatternConfig}; 
	\node[blind,left of=patternNode,node distance=3.5cm](patternNodeLeft){}; 
	\node[blind,right of=patternNode,node distance=3.5cm](patternNodeRight){};
	%
  	\node[node, above of=patternNode,node distance=2cm,fill=green!10](topkNode){P};
	\node[unboxed,below left of=topkNode,node distance=.6cm](topkNodeLabel){TopK};
	%
	\node[node, left of=topkNode,node distance=2cm,fill=green!10](middleAgedNode){P};
	\node[unboxed,below left of=middleAgedNode,node
	distance=.6cm](middleAgedNodeLabel){AgeTerms};
	%
  	\node[node, right of=topkNode,node distance=2cm,fill=green!10](myNode){P};
	\node[unboxed,below right of=myNode,node distance=.6cm](myNodeLabel){Context};
	% 		
	\path[edge,left=.1pt] (patternNode) edge node {hasRule} (middleAgedNode);
	\path[edge] (patternNode) edge node {hasRule} (topkNode);
	\path[edge,right=.1pt] (patternNode) edge node {hasRule} (myNode);
% pattern box
\node[bigbox, fit=(patternNode)(topkNode)(middleAgedNode)(myNode)
(patternNodeLabel) (topkNodeLabel) (middleAgedNodeLabel)(myNodeLabel)
(patternNodeRight)(patternNodeLeft)](patterns) {};
\node[title, right=10pt, font=\large] at (patterns.south west) {Natural Language Patterns};

% realtions among the different graphs
%
\path[edge,left=.1pt] (txtCustomer) edge node {matches}
(customerNode); \path[edge,right=.1pt] (txtMyCity) edge node {matches} (cityNode);
%
\path[edge,right=.1pt] (userCity) edge node {occursIn} (cityNode);
%
\path[edge,left=.1pt] (txtTop5) edge node {matches} (topkNode);
\path[edge,right=.1pt] (txtMiddleAged) edge node {matches} (middleAgedNode);
\path[edge,left=.1pt] (txtMyCity) edge node {matches} (myNode);

\path[edge,left=.1pt,bend left] (middleAgedNode) edge node {appliesTo} (ageNode);
\path[edge,left=.1pt,bend right] (myNode) edge node {appliesTo} (userCity);

\end{tikzpicture}
\end{center}
\vspace{-.4cm}
\caption{Used metadata and parse graph of an example question}
\label{fig:query-graph}
\vspace{-.6cm}
\end{figure}


An important foundation of the overall framework is the metadata management and
the runtime information captured in the so called \emph{parse graph}. We use the term 
\emph{parse graph} to state its close relationship to the term \emph{parse tree},
often used in the context of natural language processing. In our 
case the \emph{parse graph} and other metadata required to interpret 
a question is captured in form of 
RDF\footnote{see~\url{http://www.w3.org/RDF/}.} 
since it is a widely-accepted standard for representing graphs. We also
benefit a lot from the power of the graph pattern query language
SparQL\footnote{SPARQL Protocol and RDF Query Language} as detailed later on. 
Note that we use in the remaining paper the terms \emph{resource} 
when we refer to the actual RDF-representation and \emph{node} when we 
describe higher level concepts (even though they can be seen as synonymous
in this paper).  
% 
In figure~\ref{fig:query-graph} we show an example of a parse graph for our
example from figure~\ref{fig:translation-process} and other
graph-organized metadata.
Before discussing the parse graph itself, we like to detail the 
metadata graphs. 

On top in figure~\ref{fig:query-graph} we see a graph capturing 
the user profile and below an excerpt of the graph representing 
the data warehouse's schema. We only show one
data warehouse (see `Resorts' node) for brevity and
only one measure (`Revenue'), two dimensions 
(`Customer' and `City') and one attribute (`Age').      
The node `City' is linked to the location node (`Palo Alto')
from the user profile. Currently this link is automatically established  
by matching the values of the user profile against the warehouse's data.
%
On the bottom we see a graph capturing metadata of some configured 
natural language patterns (see next section). 
We keep this information inside RDF to relate 
these patterns to other resources. For instance the custom vocabulary
for the terms related to age  (node labeled with `AgeTerms') 
-- used to identify `middle-aged' -- applies to the schema's attribute `Age' by
its pattern definition. The user context pattern (`Context'-node) relates to
all user profile nodes that have a corresponding value in the warehouse's
data (here: `Palo Alto'). In addition, the nodes 
of the natural language pattern graph have properties
like an executable information extraction rule (see 
section~\ref{information-extraction}) and a set of variables that can 
be exported, e.g. that the `TopK'-pattern exports the number
 of items and that the ordering is ascending
 (cf. figure~\ref{fig:running-example}).

The parse graph itself is depicted in the third box from the top. It is 
generated by Information Extraction algorithms. The graph mainly consists of a central 
node representing the user's question (the larger node 
marked with `$Q$') and so-called annotation nodes 
(depicted with a rectangle shape in figure~\ref{fig:query-graph}, labeled 
with the corresponding fragment of the users' question). 
Annotation nodes capture metadata that was aquired during
the matching process (e.g., when matching data warehouse's schema 
or natural language patterns) and link to relevant resources used 
or identified during this process (e.g., a dimension or the natural language
pattern that were used).
%
As runtime metadata we keep for instance the position of a match (offset
and length of the matched fragment within the question), the type of
the occured match (e.g., match in data warehouse metadata or match with 
natural lanugage patterns) and a confidence value. In addition 
Information Extraction algorithms may capture specific metadata 
such as instantiated output variables for natural language patterns
(e.g., the `$5$' extracted from `Top 5').
%
Before going into the details on how to translate semantics captured
during the information extraction process into structured queries,
we like to detail how to derive a structure such as the one shown in 
figure~\ref{fig:query-graph} and how to configure natural language
patterns.